%==========================================================================
%=  This file is part of the Sound Restoration Project
%=  (c) Copyright Industrial Mathematics Institute
%=                University of South Carolina, Department of Mathematics
%=  ALL RIGHTS RESERVED
%=
%=  Author: Borislav Karaivanov
%==========================================================================

%==========================================================================
% List of the files on which this procedure depends:
%
% findMinRelativeDifference.m
% setLogWritingFunctHandle.m
% writeToLogFile.m
%
%==========================================================================

%==========================================================================
% The function "computeSignalOverlaps" takes a sequence of sound signals of
% the same length and computes the amount of overlap between every two
% consecutive signals.
% INPUT: "allSignalsArr" is a 2D array whose columns hold the individual
% signals whose overlaps are to be computed.
% "overlapGuess" specifies a guess for the most likely amount of overlap in
% any pair of consecutive signals. It is measured in number of samples.
% "initSearchRad" is a positive integer specifying the radius of an
% interval centered at the overlap guess where the initial search for the
% best-matching overlap is carried out. It is to reflect the belief of the
% calling function with respect to how far the best-matching overlaps are
% likely to be from the overlap guess.
% "locMinNbhdRad" is a positive integer specifying the radius of the
% interval around a sample where values of a function are checked in order
% to determine if it has a local minimum at this sample. More precisely,
% the function is considered to have a local minimum at the sample if all
% function values in the said interval are not smaller than the value at
% the central sample.
% "waitbarStruct" is an optional parameter specifying a structure of
% parameters used to set a waitbar. Those parameters are a waitbar handle,
% a starting position on the waitbar (a number between 0 and 1), a relative
% length along the waitbar (a number between 0 and (1 - starting position),
% an initial value for a counter that counts the events whose progress is
% being illustrated by the waitbar, and a total reflecting the total number
% of events of the said kind.
% "writeToLogFunctHandle" is an optional function handle which writes to a
% fixed log text file if keeping a log is requested, or does nothing
% otherwise.
% OUTPUT: "overlapArr" returns a column vector holding the amounts of
% overlap (measured in number of samples) between every two consecutive
% signals. Its length is one less than the number of all given signals.
% "minDiffArr" returns a column vector of the same length as the array of
% overlaps "overlapArr". It holds the relative average absolute difference
% between the overlapping portions of every two consecutive signals.
%==========================================================================
function [overlapArr, minDiffArr] = computeSignalOverlaps(allSignalsArr, ...
    overlapGuess, initSearchRad, locMinNbhdRad, waitbarStruct, writeToLogFunctHandle)

% Get the number of signals and their common length.
[signalLength, numSignals] = size(allSignalsArr);

% Define default values for the optional input parameters.
if (nargin < 3)
    initSearchRad = 10;
end
if (nargin < 4)
    locMinNbhdRad = 5;
end
if (nargin < 6)
    writeToLogFunctHandle = @(x) '';
end

% Allocate memory to store the computed overlaps and the corresponding
% minimal relative differences.
numPairs = numSignals - 1;
overlapArr = zeros(numPairs, 1);
minDiffArr = zeros(numPairs, 1);

% Precompute the range of overlaps to be initially searched for a local
% minimum of the realtive differences. This range will be used repeatedly.
initSearchIntLeftEnd = max(1, overlapGuess - initSearchRad);
initSearchIntRightEnd = min(signalLength, overlapGuess + initSearchRad);

% Precompute the range of overlaps for relative differences are to be
% computed initially. This range will be used repeatedly.
initMinOverlap = max(1, initSearchIntLeftEnd - locMinNbhdRad);
initMaxOverlap = min(signalLength, initSearchIntRightEnd + locMinNbhdRad);

% Compute the best-matching overlap for all pairs of consecutive signals,
% processing pairs one at a time.
for ind = 1:numPairs
    
    % Extract the two signals forming the current pair.
    firstSignalArr = allSignalsArr(:, ind).';
    secondSignalArr = allSignalsArr(:, ind + 1).';
   
    % Set the current range of overlaps for which relative differences are
    % to be computed.
    minOverlap = initMinOverlap;
    maxOverlap = initMaxOverlap;
    
    % Initialize the variable storing the smallest relative difference to
    % anything that will not be exceeded by the first actually computed
    % smallest relative difference.
    minRelDiff = inf;
    
    % Compute the relative differences over the initial range of overlaps
    % and determine the overlap corresponding to the smallest of those
    % differences.
    [newBestOverlap, newMinRelDiff] = findMinRelativeDifference(firstSignalArr, ...
        secondSignalArr, minOverlap, maxOverlap);
    
    if (newBestOverlap < initSearchIntLeftEnd)
        % If the best-matching from the initial range of overlaps is found
        % BELOW the initial search interval, then keep extending the search
        % interval to the LEFT and keep computing relative differences for
        % additional amounts of overlap until the best-matching overlap is
        % found inside the (current) search interval.
        
        % Note that this loop is always executed at least once.
        while (newMinRelDiff < minRelDiff)
            
            % Store the found better-matching overlap and the corresponding
            % smallest relative difference.
            bestOverlap = newBestOverlap;
            minRelDiff = newMinRelDiff;
            
            % Determine additional, smaller amounts of overlap for which
            % relative differences need to be computed.
            maxOverlap = max(1, minOverlap - 1);
            minOverlap = max(1, bestOverlap - locMinNbhdRad);
            
            % Compute the relative differences over the current range of
            % overlaps and determine the overlap corresponding to the
            % smallest of those differences.
            [newBestOverlap, newMinRelDiff] = findMinRelativeDifference(firstSignalArr, ...
                secondSignalArr, minOverlap, maxOverlap);
        end
        
    elseif (newBestOverlap > initSearchIntRightEnd)
        % If the best-matching from the initial range of overlaps is found
        % ABOVE the initial search interval, then keep extending the search
        % interval to the RIGHT and keep computing relative differences for
        % additional amounts of overlap until the best-matching overlap is
        % found inside the (current) search interval.
        
        % Note that this loop is always executed at least once.
        while (newMinRelDiff < minRelDiff)
            
            % Store the found better-matching overlap and the corresponding
            % smallest relative difference.
            bestOverlap = newBestOverlap;
            minRelDiff = newMinRelDiff;
            
            % Determine additional, larger amounts of overlap for which
            % relative differences need to be computed.
            minOverlap = min(signalLength, maxOverlap + 1);
            maxOverlap = min(signalLength, bestOverlap + locMinNbhdRad);
            
            % Compute the relative differences over the current range of
            % overlaps and determine the overlap corresponding to the
            % smallest of those differences.
            [newBestOverlap, newMinRelDiff] = findMinRelativeDifference(firstSignalArr, ...
                secondSignalArr, minOverlap, maxOverlap);
        end
        
    else
        % If the best-matching from the initial range of overlaps is found
        % INSIDE the initial search interval, then simply store it along
        % with the corresponding smallest relative difference.
        bestOverlap = newBestOverlap;
        minRelDiff = newMinRelDiff;
    end
    
    % Store the best-matching overlap and the corresponding relative
    % difference.
    overlapArr(ind) = bestOverlap;
    minDiffArr(ind) = minRelDiff;
    
    % Update the progress bar.
    if (exist('waitbarStruct', 'var') == 1)
        if getappdata(waitbarStruct.handle, 'canceling')
            return;
        end
        if isempty(waitbarStruct.total)
            waitbarStruct.total = numPairs;
        end
        waitbar(waitbarStruct.start + (waitbarStruct.length)*(ind/numPairs), ...
            waitbarStruct.handle, sprintf('Step %d of %d: computing overlap %d out of %d', ...
            waitbarStruct.index, waitbarStruct.totalIndices, ...
            waitbarStruct.first + ind - 1, waitbarStruct.total));
    end
end

% Write info to a log file.
aveOverlap = mean(overlapArr);
writeToLogFunctHandle(['average overlap, sound-based: ' num2str(aveOverlap)]);
writeToLogFunctHandle(['standard deviation of overlap, sound-based: ' num2str(std(overlapArr, 1))]);
writeToLogFunctHandle(['max absolute deviation of overlap, sound-based: ' num2str(max(abs(overlapArr - aveOverlap)))]);

return;
% end of the function "computeSignalOverlaps"
